package tree;

import java.awt.*;
import java.util.ArrayList;
import javax.swing.*;

import tree.BinaryTree.Node;

/**
 * Draws a graphical representation of a tree using the JFrame and JPanel
 * framework.
 */
public class TestGUI extends JFrame {

	/**
	 * A class for making a 2D line.
	 */
	private static class Line {
		Point a;
		Point b;

		private Line(Point a, Point b) {
			this.a = a;
			this.b = b;
		}
	}

	/**
	 * A panel class for painting the graphical tree
	 */
	private static class MyPanel extends JPanel {

		private static final long serialVersionUID = 1L;

		public MyPanel(int width, int height) {
			this.setOpaque(false);
			this.setBackground(Color.white);
			this.setPreferredSize(new Dimension(width, height));
		}

		@Override
		protected void paintComponent(Graphics g) {
			super.paintComponent(g);

			Font font = new Font("TimesRoman", Font.PLAIN, 15);
			int fontPad = 2;
			g.setFont(font);
			FontMetrics metrics = g.getFontMetrics(font);
			int fontHeight = metrics.getHeight();
			// int adv = metrics.stringWidth(keyString);
			// Dimension size = new Dimension(adv + fontPad, hgt + fontPad);

			// Loop over the rectangles to display
			for (int i = 0; i < treeNodeBoxes.size(); i++) {
				NodeBox r = treeNodeBoxes.get(i);

				// Draw a rectangle
				g.setColor(Color.white);
				g.fillRect(r.origin.x, r.origin.y, r.d.width, r.d.height);
				g.setColor(Color.darkGray);
				g.drawRect(r.origin.x, r.origin.y, r.d.width, r.d.height);

				// Draw a line to parent node
				g.setColor(Color.gray);
				g.drawLine(r.parentLine.a.x, r.parentLine.a.y,
						r.parentLine.b.x, r.parentLine.b.y);

				// Print the text for node key
				g.setColor(Color.black);
				g.drawString(r.key, r.origin.x + fontPad, r.origin.y
						+ fontHeight);

				// Print the height for node key
				g.setColor(Color.black);
				g.drawString(r.height, r.origin.x + fontPad, r.origin.y
						+ fontHeight * 2);

				// Print the text for node values
				g.setColor(Color.gray);
				for (int j = 0; j < r.values.size(); j++) {
					g.drawString(r.values.get(j), r.origin.x + fontPad,
							r.origin.y + fontHeight * (j + 3));
				}
			}

		}
	}

	/**
	 * A class which holds the coordinates and other data for displaying a node
	 * on the graphical tree.
	 */
	private static class NodeBox {
		Point origin;
		Dimension d;
		String key;
		String height;
		ArrayList<String> values;
		Line parentLine;

		private NodeBox(Point o, Dimension d) {
			this.origin = o;
			this.d = d;
			values = new ArrayList<String>();
		}

		public void translate(int x, int y) {
			origin.x += x;
			origin.y += y;

			parentLine.a.x += x;
			parentLine.a.y += y;

			parentLine.b.x += x;
			parentLine.b.y += y;
		}

	}

	/**
	 * Opens a window which displays a graphical representation of the tree.
	 * 
	 * @param tree
	 */
	public static void displayTree(BinaryTree tree) {

		int nodeBoxWidth = 300;
		int nodeBoxHeight = 150;

		int nodeBoxXPad = 25;
		int nodeBoxYPad = 25;

		Node root = tree.root;

		// Check depth of the tree, calculate max amount of nodes at lowest
		int nodeGridHeight = maxDepth(root);
		int nodeGridWidth = (int) Math.pow(2, nodeGridHeight - 1);

		// Create a 2D grid of nodes
		Node[][] nodeGrid = new Node[nodeGridHeight][nodeGridWidth];
		nodeGrid[0][0] = root;

		// Pad the tree with empty nodes until it is balanced at max depth.
		// Populate the node grid, then remove any empty nodes from the grid.
		padTreeWithEmptyNodes(root, nodeGridHeight);
		populateNodeGrid(nodeGrid, root, 0);
		removeEmptyNodesFromGrid(nodeGrid);
		printNodeGrid(nodeGrid);

		// Calculate the maximum canvas size needed for this tree
		int canvasWidth = (nodeBoxWidth + nodeBoxXPad) * nodeGridWidth
				+ nodeBoxXPad;
		int canvasHeight = (nodeBoxHeight + nodeBoxYPad) * nodeGridHeight
				+ nodeBoxYPad;

		// Create the graphical rectangles and their connections
		generateNodeBoxTree(nodeGrid, canvasWidth, nodeBoxWidth, nodeBoxHeight,
				nodeBoxYPad);

		// Find leftmost and rightmost rectangle in order to crop away any empty
		// horizontal space on the canvas.
		int leftMost = canvasWidth;
		int rightMost = 0;
		for (NodeBox nodeBox : treeNodeBoxes) {
			int leftBoundary = nodeBox.origin.x;
			int rightBoundary = nodeBox.origin.x + nodeBoxWidth;
			if (leftBoundary < leftMost) {
				leftMost = leftBoundary;
			} else if (rightBoundary > rightMost) {
				rightMost = rightBoundary;
			}
		}
		canvasWidth = rightMost - leftMost;

		// Translate all rectangles and lines to fit the cropped canvas
		for (NodeBox nodeBox : treeNodeBoxes) {
			nodeBox.translate(-leftMost, 0);
		}

		// Run the GUI to show the tree image
		final int windowWidth = canvasWidth;
		final int windowHeight = canvasHeight;
		EventQueue.invokeLater(new Runnable() {

			@Override
			public void run() {
				new TestGUI(windowWidth, windowHeight);
			}
		});
	}

	/**
	 * Calculates the positions on canvas for the nodes in the grid. Creates
	 * rectangle objects which contains their coordinates, connection lines to
	 * parents, key and values.
	 * 
	 * @param nodeGrid
	 * @param canvasWidth
	 * @param nodeBoxWidth
	 * @param nodeBoxHeight
	 * @param nodeBoxYPad
	 */
	private static void generateNodeBoxTree(Node[][] nodeGrid, int canvasWidth,
			int nodeBoxWidth, int nodeBoxHeight, int nodeBoxYPad) {

		int nodeGridHeight = nodeGrid.length;
		int nodeGridWidth = nodeGrid[0].length;

		for (int i = nodeGridHeight - 1; i >= 0; i--) {

			int xStep = (int) ((canvasWidth) / (Math.pow(2, i)));
			int yOffset = i * (nodeBoxHeight + nodeBoxYPad);

			int pXStep = (int) ((canvasWidth) / (Math.pow(2, i - 1)));
			int pYOffset = (i - 1) * (nodeBoxHeight + nodeBoxYPad);

			for (int j = 0; j < nodeGridWidth; j++) {

				Node node = nodeGrid[i][j];

				if (node == null) {
					continue;
				}

				int nodeX = xStep * (j + 1) - xStep / 2;
				int nodeY = yOffset;

				Point nodePoint = new Point(nodeX, nodeY);
				Dimension nodeDim = new Dimension(nodeBoxWidth, nodeBoxHeight);

				NodeBox nodeRect = new NodeBox(nodePoint, nodeDim);
				nodeRect.key = node.key;
				nodeRect.values.addAll(node.translations);
				nodeRect.height = Integer.toString(node.height);

				if (i > 0) {
					// int pi = i - 1;
					int pj = (int) Math.floor((double) j / 2);

					int pNodeX = pXStep * (pj + 1) - pXStep / 2;
					int pNodeY = pYOffset;

					Point pNodePoint = new Point(pNodeX + nodeBoxWidth / 2,
							pNodeY + nodeBoxHeight);
					Point qNodePoint = new Point(
							nodePoint.x + nodeBoxWidth / 2, nodePoint.y);

					nodeRect.parentLine = new Line(qNodePoint, pNodePoint);

				} else {
					Point pNodePoint = new Point(nodePoint);
					nodeRect.parentLine = new Line(pNodePoint, pNodePoint);
				}
				treeNodeBoxes.add(nodeRect);
			}
		}
	}

	/**
	 * Find max depth of the tree.
	 * 
	 * @param node
	 * @return
	 */
	private static int maxDepth(Node node) {
		if (node == null)
			return 0;
		else {
			int leftDepth = maxDepth(node.left);
			int rightDepth = maxDepth(node.right);

			if (leftDepth > rightDepth)
				return (leftDepth + 1);
			else
				return (rightDepth + 1);
		}
	}

	/**
	 * Pads any empty places on the tree with empty nodes.
	 * 
	 * @param node
	 * @param depth
	 */
	private static void padTreeWithEmptyNodes(Node node, int depth) {
		if (depth == 1) {
			return;
		} else {
			if (node.left == null) {
				node.left = new Node("", "");
			}
			if (node.right == null) {
				node.right = new Node("", "");
			}
			padTreeWithEmptyNodes(node.left, depth - 1);
			padTreeWithEmptyNodes(node.right, depth - 1);
		}
	}

	/**
	 * Links nodes from the tree to the grid.
	 * 
	 * @param nodeGrid
	 * @param node
	 * @param level
	 */
	private static void populateNodeGrid(Node[][] nodeGrid, Node node, int level) {
		if (node.left == null || node.right == null) {
			return;
		}
		populateNodeGrid(nodeGrid, node.left, level + 1);
		Node[] row = nodeGrid[level + 1];
		for (int i = 0; i < row.length; i++) {
			if (row[i] == null) {
				row[i] = node.left;
				row[i + 1] = node.right;
				break;
			}
		}
		populateNodeGrid(nodeGrid, node.right, level + 1);
	}

	/**
	 * Print a string representation of the node grid.
	 * 
	 * @param nodeGrid
	 */
	private static void printNodeGrid(Node[][] nodeGrid) {
		for (int i = 0; i < nodeGrid.length; i++) {

			StringBuffer b = new StringBuffer();

			for (int j = 0; j < nodeGrid[0].length; j++) {
				Node n = nodeGrid[i][j];
				if (n == null) {
					b.append("_");
				} else {
					b.append(n.key);
				}
			}
			System.out.println(b.toString());
		}
	}

	/**
	 * Removes any empty nodes from the grid.
	 * 
	 * @param nodeGrid
	 */
	private static void removeEmptyNodesFromGrid(Node[][] nodeGrid) {
		for (int i = 0; i < nodeGrid.length; i++) {
			for (int j = 0; j < nodeGrid[0].length; j++) {
				Node n = nodeGrid[i][j];
				if (n != null && n.key == "") {
					nodeGrid[i][j] = null;
				}
			}
		}
	}

	private static final long serialVersionUID = 1L;

	static ArrayList<NodeBox> treeNodeBoxes = new ArrayList<NodeBox>();

	public TestGUI(int width, int height) {
		JViewport viewport = new JViewport();
		viewport.setView(new MyPanel(width, height));
		JScrollPane scrollPane = new JScrollPane();
		scrollPane.setViewport(viewport);
		this.add(scrollPane);
		this.setDefaultCloseOperation(DISPOSE_ON_CLOSE);
		this.pack();
		this.setLocationRelativeTo(null);
		this.setVisible(true);
	}

}
